package com.zdb.demo.java.leetcode.q4medianoftwosortedarrays;

public class Solution {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,3};
        int[] nums2 = new int[]{2};

        System.out.println(findMedianSortedArrays2(nums1, nums2));
    }


    /**
     * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
     * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     * 你可以假设 nums1 和 nums2 不会同时为空。
     * 示例 1:
     * > nums1 = [1, 3]
     * > nums2 = [2]
     *
     * 则中位数是 2.0
     * 示例 2:
     * > nums1 = [1, 2]
     * > nums2 = [3, 4]
     *
     * 则中位数是 (2 + 3)/2 = 2.5
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // TODO 实现 log(m + n)
        return 0.0d;
    }

    /**
     * 实现 (m + n)
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {

        int mergeArrLength = (nums1.length + nums2.length) / 2 + 1;

        int[] mergeArr = new int[mergeArrLength];

        int tmp = Math.min(nums1[0], nums2[0]) ;
        int tmpArrIdx = 0;

        int idx1 = 0;
        int idx2 = 0;
        while(tmpArrIdx < mergeArrLength) {
            if(nums1[idx1] < nums2[idx2]) {
                mergeArr[tmpArrIdx] = nums1[idx1];
                idx1++;
            } else {
                mergeArr[tmpArrIdx] = nums2[idx2];
                idx2++;
            }
            tmpArrIdx ++;
        }

        if((nums1.length + nums2.length) %2 == 0) {
            return (mergeArr[mergeArrLength-1] + mergeArr[mergeArrLength-2]) / 2.0d;
        } else {
            return mergeArr[mergeArrLength-1];
        }
    }

}